//给定一个字符串 S，计算 S 的不同非空子序列的个数。 
//
// 因为结果可能很大，所以返回答案模 10^9 + 7. 
//
// 
//
// 示例 1： 
//
// 输入："abc"
//输出：7
//解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
// 
//
// 示例 2： 
//
// 输入："aba"
//输出：6
//解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
// 
//
// 示例 3： 
//
// 输入："aaa"
//输出：3
//解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
// 
//
// 
//
// 
//
// 提示： 
//
// 
// S 只包含小写字母。 
// 1 <= S.length <= 2000 
// 
//
// 
//
// 
// Related Topics 字符串 动态规划 
// 👍 93 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：不同的子序列 II
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P940_DistinctSubsequencesIi {
    public static void main(String[] args) {
        Solution solution = new P940_DistinctSubsequencesIi().new Solution();
        String str = "zchmliaqdgvwncfatcfivphddpzjkgyygueikthqzyeeiebczqbqhdytkoawkehkbizdmcnilcjjlpoeoqqoqpswtqdpvszfaksn";
        MyUtil.print(solution.distinctSubseqII(str));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int distinctSubseqII(String str) {
            if (str == null || str.length() == 0) {
                return 0;
            }
            int mod = 1000000007;
            char[] strs = str.toCharArray();
            int[] pre = new int[26];
            int res = 1; // 初始一个空集合
            for (int i = 0; i < strs.length; i++) {
                // 新加入的
                int newAdd = res;
                // 当前字符的坐标
                int preIndex = strs[i] - 'a';
                // 总和为 之前的 + 新加入的 - 上一个以当前字符结尾的
                res = (res + newAdd) % mod;
                res = (res - pre[preIndex] + mod) % mod;
                // 设置当前字符结尾的数量
                pre[preIndex] = newAdd;
            }
            return res - 1; // 最后减一个空集合
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}